本文参考了 《Generating Functionology》Chapter 3 的内容

某天，有人（不是我）问了如下问题（不用考虑任何置换），

学习了 $\text{Exponential Family}$ ，我们可以轻松解决上述问题。

一个 $\text{Card} \space C(S,p)$ 是一个包含有限集 $S \subset \N_+$ 和一个描述 $S$ 的图片（包括图）的二元组。

它的权值为 $|S|$ ，若 $S = [n]$ ，则该 $\text{Card}$ 被称为标准的。

一个 $\text{Hand} \space $ 为一些 $\text{Card}$ 的集合，满足对于给定的 $n$ ，有 $\sum |S_i| = n$ 且 $\cup S_i = [n]$ ，即它们可以恰好凑成 $[n]$ 。

它的权值为 $\sum |S_i|$ 。

一个 $\text{Deck}$ 是若干权值相同的标准 $\text{Card}$ 集合，记 $d_i= |D_i|$ ，

$D(x)$ 为 $\{d_i\}$ 的 $EGF$ 。

一个指数族（乱翻译的）$\mathcal{F}$ 则包含了 $D_1,D_2,...$ 。

$h(n,k)$ 表示权值为 $n$ 且恰好有$k$ 个数 $\text{Card}$ 的 $\text{Hand}$ 个数，

令 $\large \mathcal{H}(x,y)=\sum_{n,k \geq 0}h(n,k)\frac{x^n}{n!}y^k $ 。

如果省略 $y$ 或 $k$ ，例如 $h(n)$ 、$\mathcal{H}(x)$ 表示所有合法的 $y$ 之和。

对于一个 $\mathcal{F}$ ，有

$\large \mathcal{H}(x,y)= \exp\{yD(x)\} $.

为了证明上述定理，首先我们介绍如下引理：

令 $\mathcal{F^{'}} ,F^{''}$ 为两个指数族，且它们的 $\text{Hand}$ 互不相同，$\mathcal{F} = \mathcal{F^{'}} \oplus F^{''}$ 为它们的合并，则有 $\mathcal{H}(x,y)=\mathcal{H}^{'}(x,y)\mathcal{H}^{''}(x,y)$。

证明：

注意到

$\large h(n,k)=\sum_{n_1,k_1 \geq 0} \binom{n}{n_1} h^{'}(n_1,k_1)h^{''}(n-n_1,k-k_1)$

其意义为选定 $n$ 的一个 $n_1$ 大小子集，然后再从其中任选 $k_1$ 个 $\text{Card}$ 。

而右式 $= [\frac{x^n}{n!}y^k] \mathcal{H}^{'}(x,y)\mathcal{H}^{''}(x,y) $ .

$\square$

接下来我们考虑仅有一个 $D_i$ 非零，的情况，则 $h(n,k)$ 只能在 $ h(ki,k) $ 处有值。

不妨令 $n = ik$，由于所有 $\text{Card}$ 的都是从 $D_i$ 当中选择，因此最后需要除以 $k!$ 。

也就是说：

$\large h(ki,k)=d_i^k\frac{n!}{i!^k}\frac{1}{k!}$ ，

从而有$$ \mathcal{H}(x,y) = \sum_{n,k \geq 0}h(n,k)\frac{x^n}{n!}y^k = \sum_k h(n,k) \frac{x^{ik}}{n!}y^k = \sum_k \frac{d_i^kx^{ik}y^k}{k!(i!)^k} = \exp\{\frac{y\times d_ix^i}{i!}\} $$

然后，我们再考虑将不同的 $D_i$ 合并在一起，不妨认为仅由 $D_i$ 产生的 $\text{Hand}$ 的生成函数记作 $\mathcal{H}_i(x,y)$ ，有引理知，我们有：$$ \mathcal{H}(x,y)=\prod_{i\geq1}H_i(x,y)= \exp\{y\sum_{i \geq 1} \frac{d_ix^i}{i!}\}=\exp\{yD(x)\} $$$\square$

容易发现大小为 $i$ 的圆排列 $d_i = (i-1)!$ ，从而 $D(x)=\sum_{i\geq1}\frac{x^n}{n}=\log\frac{1}{1-x}$，

因此 $\mathcal{H}(x,y)=e^{yD(x)}=\frac{1}{(1-x)^y}$。

大小为 $i$ 的子集只有 $1$ 个，因此 $D(x) = e^x-1$ ，

从而 $\mathcal{H}(x,y)=e^{y(e^x-1)}$。

$ \mathcal{H} (x)=e^{e^x-1}$ 其实就是著名的贝尔数的 $EGF$。

如果一个 $\text{Hand}$ 表示一个图，

那么一个 $\text{Deck}$ 就表示一个连通图。

而显然，$\mathcal{H}(x)=\sum_{n\geq0}2^{\binom{n}{2}}\frac{x^n}{n!}$，

因此 $D(x)=\log \mathcal{H}(x)$，

首先考虑如果黑白两色可以区分，

则 $h_i=\sum_{k\geq0}\binom{n}{k}2^{k(n-k)}$ ，

从而有 $D(x)=\log \mathcal{H}_0(x)$ ，

但是不考虑颜色，我们会有 $\mathcal{H}(x)=\exp \frac{D(x)}{2}=\sqrt{\mathcal{H_0}(x)}$。

思考：如何计算每个点度数都为 2 的图的个数？